C/C++ Users Group Library 1996 July

home *** CD-ROM | disk | FTP | other *** search

/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 247_02 / manual2.doc < prev next >

Wrap

Text File | 1989-04-17 | 59.6 KB | 2,641 lines

Appendix III - MIRACL routines Note: In these routines a big parameter can also be used wherever a flash is specified, but not visa-versa. Further information may be gleaned from the (lightly) commented source code. Function: void absol(x,y) absol flash x,y; Module: bncore.c Description: Gives absolute value of a big or flash number. Parameters: Two big/flash variables x and y. On exit y=abs(x). Return value: None Restrictions: None See also: negate Function: void add(x,y,z) add big x,y,z; Module: bnarth0.c Description: Adds two big numbers. Parameters: Three big numbers x, y and z. On exit z=x+y. Return value: None Restrictions: None See also: subtract, incr, decr. Example: add(x,x,x); This doubles the value of x. Function: void bigdig(x,n,b) bigdig big x; int n,b; Module: bnrand.c Description: Generates a big random number of given length. Parameters: A big number x and two integers n and b. On exit x contains a big random number n digits long to base b. Return value: None Restrictions: None See also: bigrand Example: bigdig(x,100,10); This generates a 100 decimal digit random number x Function: void bigrand(w,x) bigrand big w,x; Module: bnrand.c Description: Generates a big random number. Parameters: Two big numbers w and x. On exit x is a big random number in the range 1<x<w. Return value: None Restrictions: None See also: bigdig Function: int brand() brand Module: bncore.c Description: Generates random integer number Parameters: None Return Value: A random integer number Restrictions: First use must be preceded by an initial call to irand. See also: irand, bigrand, bigdig, frand. Function: void build(x,gener) build flash x; int (*gener)(); Module: bnbuild.c Description: Uses supplied generator of regular continued fraction expansion to build up a flash number, rounded if necessary. Parameters: The flash number created, and the generator function. Return value: None Restrictions: None See also: round, froot, fexp, ftan Example: int phi(w,n) flash w; int n; { /* rcf generator for golden ratio */ return 1; } . . build(x,phi); . This will calculate the golden ratio in x - very quickly! Function: int cinnum(x,f) cinnum flash x; FILE *f; Module: bnio2.c Description: Inputs a flash number from the keyboard, a file or a string, using as number base the current value of the global variable IOBASE. Flash numbers can be entered using either a slash '/' to indicate numerator and denominator, or with a radix point. Parameters: A big/flash number x and a file descriptor f. For input from the keyboard specify f as stdin, otherwise as the descriptor of some other opened file. To input from a string copy the string to the global character array IBUFF before calling cinnum. In this case the file descriptor will be ignored and input taken from IBUFF instead. To force input of a fixed number of bytes, set global INPLEN to the required number, just before calling cinnum. Return value: The number of input characters. Restrictions: None See also: innum, otnum, cotnum Example: char* chex="AF1298065BFE4C96DB723A"; . IOBASE=16; strcpy(IBUFF,chex); cinnum(x,stdin); This will input the large hex number chex into the big variable x. IOBASE=256; INPLEN=25; cinnum(x,fp); This will input 25 bytes from the file associated with fp, and convert them into a big positive number x. Function: int compare(x,y) compare big x,y; Module: bncore.c Description: Compares two big numbers. Parameters: Two big numbers x and y. Return value: Returns +1 if x>y, returns 0 if x=y, returns -1 if x<y. Restrictions: None See also: fcomp Function: void convert(n,x) convert int n; big x; Module: bncore.c Description: Convert an integer number to big number format. Parameters: An integer n and a big number x. Return value: None Restrictions: None See also: fconv, lconv, dconv Function: void copy(x,y) copy flash x,y; Module: bncore.c Description: Copies a big or flash number to another. Parameters: Two big or flash numbers x and y. On exit y=x. Note that if x and y are the same variable, no operation is performed. Return value: None Restrictions: None See also: - Function: int cotnum(x,f) cotnum flash x; FILE *f; Module: bnio2.c Description: Output a big or flash number to the screen or to a file, using as number base the value currently assigned to the global variable IOBASE. A flash number will be converted to radix-point representation if the global variable POINT=ON. Otherwise it will be output as a fraction. If the global variable WRAP=ON, numbers too large to be represented on one line are 'wrapped around' onto the next line. Parameters: A big/flash number x and a file descriptor f. If f is stdout then output will be to the screen, otherwise to the file opened with descriptor f. Return value: Number of output characters. Restrictions: None See also: innum, cinnum, otnum. Example: IOBASE=256 cotnum(x,fp); This outputs x (in pure binary) as a byte array, to the file associated with fp. Function: void dconv(d,x) dconv double d; flash x; Module: bnflash.c Description: Converts a double to flash format. Parameters: A double d and a flash variable x. On exit x will contain the flash equivalent of d. Return value: None Restrictions: None See also: fdsize, lconv, convert,fconv Function: void decr(x,n,z) decr big x,z; int n; Module: bnarth0.c Description: Decrement a big number by an integer amount. Parameters: Big numbers x and z, and integer n. On exit z=x-n. Return value: None Restrictions: None See also: add, subtract, incr. Example: decr(x,2,x); /* This decrements x by 2. */ Function: void denom(x,y) denom flash x; big y; Module: bncore.c Description: Extract the denominator of a flash number into a big number Parameters: A flash number x and a big number y. On exit y will contain the denominator of x. Return value: None Restrictions: None See also: numer, fpack. Function: void divide(x,y,z) divide big x,y,z; Module: bnarth2.c Description: Divides one big number by another. Parameters: Three big numbers x, y and z. On exit z=x/y; x=x mod y. The quotient only is returned if x and z are the same, the remainder only if y and z are the same. Return value: None Restrictions: Parameters x and y must be different, and y must be non-zero. See also: multiply, mad Example: divide(x,y,y); This sets x equal to the remainder when x is divided by y. The quotient is not returned. Function: void expb2(x,n) expb2 big x; int n; Module: bnarth3.c Description: Calculates 2 to the power of an integer. Parameters: A big number x and an integer n. On exit x=2^n. Return value: None Restrictions: None See also: logb2 Example: expb2(x,216091); decr(x,1,x); cotnum(x,stdout); This calculates and prints out the largest known prime number (on a true 32-bit computer). Function: int exsign(x) exsign flash x; Module: bncore.c Description: Extracts the sign of a big/flash number. Parameters: A big/flash number x. Return value: The sign of x, i.e. -1 if x is negative, +1 if x is zero or positive. Restrictions: None See also: insign Function: void facos(x,y) facos flash x,y; Module: bnflsh3.c Description: Calculates arc-cosine of a flash number, using fasin. Parameters: Two flash numbers x and y. On exit y=acos(x). Return value: None Restrictions: |x| must be less than or equal to 1. See also: fatan, fasin Function: void facosh(x,y) facosh flash x,y; Module: bnflsh4.c Description: Calculates hyperbolic arc-cosine of a flash number. Parameters: Two flash numbers x and y. On exit y=acosh(x). Return value: None Restrictions: |x| must be greater than or equal to 1. See also: fatanh, fasinh Function: void fadd(x,y,z) fadd flash x,y,z; Module: bnflash.c Description: Add two flash numbers. Parameters: Three flash numbers x, y and z. On exit z=x+y. Return value: None Restrictions: None See also: fsub, fincr Function: void fasin(x,y) fasin flash x,y; Module: bnflsh3.c Description: Calculates arc-sin of a flash number, using fatan. Parameters: Two flash numbers x and y. On exit y=asin(x). Return value: None Restrictions: |x| must be less than or equal to 1. See also: facos, fatan Function: void fasinh(x,y) fasinh flash x,y; Module: bnflsh4.c Description: Calculates hyperbolic arc-sin of a flash number. Parameters: Two flash numbers x and y. On exit y=asinh(x). Return value: None Restrictions: None See also: facosh, fatanh Function: void fatan(x,y) fatan flash x,y; Module: bnflsh3.c Desciption: Calculates the arc-tangent of a flash number, using O(n^2.5) method based on Newton's iteration. Parameters: Two flash numbers x and y. On exit y=atan(x). Return value: None Restrictions: None See also: fasin, facos Function: void fatanh(x,y) fatanh flash x,y; Module: bnflsh4.c Desciption: Calculates the hyperbolic arc-tangent of a flash number. Parameters: Two flash numbers x and y. On exit y=atanh(x). Return value: None Restrictions: x.x must be less than 1 See also: fasinh, facosh Function: int fcomp(x,y) fcomp flash x,y; Module: bnflash.c Description: Compare two flash numbers. Parameters: Two flash numbers x and y. Return value: Returns -1 if y>x, +1 if x>y and 0 if x=y. Restrictions: None See also: compare Function: void fconv(n,d,x) fconv int n,d; flash x; Module: bnflash.c Description: Convert a simple fraction to flash format. Parameters: Integers n and d, and a flash number x. On exit x={n/d} Return value: None Restrictions: None See also: convert, lconv, dconv Function: void fcos(x,y) fcos flash x,y; Module: bnflsh3.c Description: Calculates cosine of a given flash angle, using ftan. Parameters: Two flash numbers x and y. On exit y=cos(x). Return value: None Restrictions: None See also: fsin, ftan Function: void fcosh(x,y) fcosh flash x,y; Module: bnflsh4.c Description: Calculates hyperbolic cosine of a given flash angle. Parameters: Two flash numbers x and y. On exit y=cosh(x). Return value: None Restrictions: None See also: fsinh, ftanh Function: void fdiv(x,y,z) fdiv flash x,y,z; Module: bnflash.c Description: Divides two flash numbers. Parameters: Three big numbers x,y and z. on exit z=x/y. Return value: None Restrictions: None See also: fmul, fpmul Function: double fdsize(x) fdsize flash x; Module: bndouble.c Description: Converts a flash number to double format. Parameters: A flash number x. Return value: The value of the parameter x as a double. Restrictions: The value of x must be less than BIGGEST. See mirdef.h See also: dconv Function: void fexp(x,y) fexp flash x,y; Module: bnflsh2.c Description: Calculates the exponential of a flash number using O(n^2.5) method. Parameters: Two flash numbers x and y. On exit y=exp(x). Return value: None Restrictions: None See also: flog, fpowf Function: void fincr(x,n,d,y) fincr big x,y; int n,d; Module: bnflash.c Description: Add a simple fraction to a flash number. Parameters: Two flash numbers x and y, and two integers n and d. On exit y=x+{n/d}. Return value: None Restrictions: None See also: fadd, fsub Example: fincr(x,-2,3,x); This subtracts two-thirds from the value of x. Function: void flog(x,y) flog flash x,y; Module: bnflsh2.c Description: Calculates the natural log of a flash number using O(n^2.5) method. Parameters: Two flash numbers x and y. On exit y=log(x). Return value: None Restrictions: None See also: fexp, fpowf Function: void flop(x,y,op,z) flop flash x,y,z; int *op; Module: bnflash.c Description: Perform primitive flash operation. Used internally. Parameters: Three flash numbers x,y and z. On exit z=Fn(x,y), where the function performed depends on the parameter op. See source listing comments for more details. Restrictions: None Return value: None See also: fadd, fsub, fmul, fdiv Function: void fmul(x,y,z) fmul flash x,y,z; Module: bnflash.c Description: Multiply two flash numbers. Parameters: Three flash numbers x,y and z. On exit z=x*y. Return value: None Restrictions: None See also: fpmul, fdiv Function: void fpack(n,d,x) fpack flash x; big n,d; Module: bncore.c Description: Forms a flash number from big numerator and denominator. Parameters: A flash number x and two big numbers n and d. On exit x={n/d}. Return value: None Restrictions: The denominator must be non-zero. Flash variable x and big variable d must be distinct. The resulting flash variable must not be too big for the representation. See also: numer, denom. Function: void fpi(x) fpi flash x; Module: bnpi.c Description: Calculates pi using Guass-Legendre O(n².log(n)) method. Note that on subsequent calls to this routine, pi is immediately available, as it is stored internally. Parameters: A flash number x. On exit x=pi. Return value: None Restrictions: None. See also: fsin, fcos, ftan Function: void fpower(x,n,y) fpower flash x,y; int n; Module: bnflsh1.c Description: Raises a flash number to an integer power. Parameters: Flash variables x and y, and an integer n. On exit y=x^n. Return value: None Restrictions: None See also: froot Function: void fpmul(x,n,d,y) fpmul flash x,y; int n,d; Module: bnflash.c Description: Multiplies a flash number by a simple fraction. Parameters: Two flash numbers x and y, and two integers n and d. On exit y=x.{n/d} Return value: None Restrictions: None See also: fmul, fdiv Function: void fpowf(x,y,z) fpowf flash x,y,z; Module: bnflsh2.c Description: Raises a flash number to a flash power. Parameters: Three flash numbers x, y and z. On exit z=x^y Return value: None Restrictions: None See also: fexp, flog Function: void frand(x) frand flash x; Module: bnrand.c Description: Generates a random flash number. Parameters: A big number x. On exit x contains a flash random number in the range 0<x<1. Return value: None Restrictions: None See also: bigrand, bigdig Function: void frecip(x,y) frecip flash x,y; Module: bnflash.c Description: Calculates reciprocal of a flash number. Parameters: Two flash numbers x and y. On exit y=1/x. Return value: None Restrictions: None See also: fdiv, fmul Function: bool froot(x,m,y) froot flash x,y; int m; Module: bnflsh1.c Description: Calculates m-th root of a flash number using Newton's O(n²) method. Parameters: Flash numbers x and y, and an integer m. On exit y is the m-th root of x. Return value: TRUE for exact root, otherwise FALSE Restrictions: None See also: fpower Function: void fsin(x,y) fsin flash x,y; Module: bnflsh3.c Description: Calculates sine of a given flash angle. Uses ftan. Parameters: Two flash numbers x and y. On exit y=sin(x). Return value: None Restrictions: None See also: fcos, ftan Function: void fsinh(x,y) fsinh flash x,y; Module: bnflsh4.c Description: Calculates hyperbolic sine of a given flash angle. Parameters: Two flash numbers x and y. On exit y=sinh(x). Return value: None Restrictions: None See also: fcosh, ftanh Function: void fsub(x,y,z) fsub flash x,y,z; Module: bnflash.c Description: Subtract two flash numbers. Parameters: Three flash numbers x,y and z. On exit z=x-y. Return value: None Restrictions: None See also: fadd, fincr Function: void ftan(x,y) ftan flash x,y; Module: bnflsh3.c Description: Calculates the tan of a given flash angle, using an O(n²√n) method. Parameters: Two flash numbers x and y. On exit y=tan(x). Return value: None Restrictions: None See also: fsin, fcos Function: void ftanh(x,y) ftanh flash x,y; Module: bnflsh4.c Description: Calculates the hyperbolic tan of a given flash angle. Parameters: Two flash numbers x and y. On exit y=tanh(x). Return value: None Restrictions: None See also: fsinh, fcosh Function: void ftrunc(x,y,z) ftrunc flash x,z; big y; Module: bnflash.c Description: Seperates a flash number to a big number and a flash remainder. Parameters: Flash numbers x and z, and a big number y. On exit y=int(x) and z = x-y (the fractional remainder). if y is the same as z, only int(x) is returned. Return value: None Restrictions: None Function: int gcd(x,y,z) gcd big x,y,z; Module: bngcd.c Description: Calculates the Greatest Common Divisor of two big numbers. Parameters: Three big numbers x, y and z. On exit z=gcd(x,y) Return value: GCD as integer, if possible, otherwise TOOBIG Restrictions: None See also: xgcd, round Function: int getdig(x,i) getdig big x; int i; Module: bncore.c Description: Extracts a digit from a big number. Parameters: A big number x, and the required digit i. Return value: The value of the requested digit. Restrictions: Returns rubbish if required digit does not exist. See also: putdig, numdig. Function: int *gprime(n) *gprime int n; Module: bnsmall.c Description: Generates an array of all prime numbers up to a certain limit, terminated by zero. Parameters: A positive integer n indicating the maximum prime number to be generated, or a negative integer indicating that (-n) primes are to be generated. Return value: A pointer to the prime number array. Restrictions: None See also: - Function: int igcd(x,y) igcd int x,y; Module: bncore.c Description: Calculates the Greatest Common Divisor of two integers using Euclids Method. Parameters: Two integers x and y Return value: The GCD of x and y See also: gcd Function: void incr(x,n,z) incr big x,z; int n; Module: bnarth0.c Description: Increment a big variable. Parameters: Big numbers x and z, and an integer n. On exit z=x+n. Return value: None Restrictions: None See also: add, subtract, decr. Function: int innum(x,f) innum flash x; FILE *f; Module: bnio1.c Description: Inputs a big or flash number from a file, the keyboard or a string. Flash numbers can be entered using either a slash '/' to indicate numerator and denominator, or with a radix point. Parameters: A big/flash number x and a file descriptor f. For input from the keyboard specify f as stdin, otherwise as the descriptor of some other opened file. To input from a string, copy the string to the global character array IBUFF before calling innum. In this case the file descriptor will be ignored, and input taken directly from IBUFF. Return value: The number of characters input. Restrictions: The number base specified in mirsys must be less than or equal to 256. If not use cinnum instead. See also: otnum, cinnum, cotnum. Function: void insign(s,x) insign int s; flash x; Module: bncore.c Description: Forces a big/flash number to a particular sign. Parameters: A big/flash number x, and the sign s that it is to take. On exit x=s*abs(x). Return value: None Restrictions: None See also: exsign. Example: insign(PLUS,x); /* force x to be positive */ Function: int inverse(x,y) inverse int x,y; Module: bnsmall.c Description: Calculates the inverse of an integer modulus a co- prime integer Parameters: An integer x and a co-prime integer y Return value: 1/x mod y Restrictions: Return value is unpredictable if x and y are not co- prime See also: igcd, sqrmp Function: void irand(seed) irand long seed; Module: bncore.c Description: Initializes random number system. Uses Knuth's subtractive method. Long integer types are used internally to yield a generator with maximum period. Parameters: A long integer seed, which is used to start off the random number generator. Return value: None Restrictions: None See also: brand, bigrand, bigdig, frand. Function: void lconv(ln,x) lconv long n; big x; Module: bncore.c Description: Converts a long integer to big number format Parameters: A long integer ln and a big number x Return value: None Restrictions: None See also: convert, fconv, dconv Function: int logb2(x) logb2 big x; Module: bnarth3.c Description: Calculates the approximate integer log to the base 2 of a big number (in fact the number of bits in it.) Parameters: A big number x. Return value: Number of bits in x Restrictions: None See also: expb2 Function: void mad(x,y,z,w,q,r) mad big x,y,z,w,q,r; Module: bnarth2.c Description: Multiply add and divide big numbers. The initial product is stored in a double-length internal variable to avoid the possibility of overflow at this stage. Parameters: Six big numbers x,y,z,w,q and r. On exit q=(x*y+z)/w and r contains the remainder. If w and q are not distinct variables then only the remainder is returned; if q and r are not distinct then only the quotient is returned. The addition of z is not done if x and z (or y and z) are the same. Return value: None Restrictions: Parameters w and r must be distinct. The value of w must not be zero. See also: multiply, divide. Example: mad(x,x,x,w,x,x); This sets x=(x*x)/w. The remainder is not returned. Function: void mirsys(nd,nb) mirsys int nd,nb; Module: bncore.c Description: Initialize the MIRACL system as described below. Must be called before attempting to use any other MIRACL routines. (1) The error tracing mechanism is initialised. (2) the number of computer words to use for each big/flash number is calculated from nd and nb. (3) Sixteen big work variables (four of them double length) are initialised. (4) Certain global variables are given default initial values. (5) The random number generator is started by calling irand(0L). Parameters: The number of digits nd to use for each big/flash variable and the number base nb. If nd is negative it is taken as indicating the size of big/flash numbers in 8-bit bytes. Return value: None Restrictions: The number base nb must be greater than 1 and less than or equal to MAXBASE. The number of digits nd must be less than a certain maximum, depending on the value of BTS. (See mirdef.h). See also: irand, mirvar. Example: mirsys(500,10); This initializes the MIRACL system to use 500 decimal digits for each big or flash number. Function: flash mirvar(iv) mirvar int iv; Module: bncore.c Description: Initialises a big/flash variable by reserving a suitable number of memory locations for it. Parameters: An integer initial value for the big/flash number. Return Value: A pointer to the reserved locations. Restrictions: None See also: mirsys Example: flash x; x=mirvar(1); Creates a flash variable x=1. Function: void multiply(x,y,z) multiply big x,y,z; Module: bnarth2.c Description: Multiplies two big numbers Parameters: Three big numbers x,y and z. On exit z=x.y Return value: None Restrictions: None See also: divide, mad Function: void negate(x,y) negate flash x,y; Module: bncore.c Description: Negates a big/flash number. Parameters: Two big/flash numbers x and y. On exit y=-x. Return value: None Restrictions: None. Note that negate(x,x) is valid and sets x=-x. See also: absol. Function: int numdig(x) numdig big x; Module: bncore.c Description: Calculates the number of digits in a big number. Parameters: A big number x. Return value: The number of digits in x. Restrictions: None See also: getdig, putdig. Function: void numer(x,y) numer flash x; big y; Module: bncore.c Description: Extract the numerator of a flash number. Parameters: A flash number x and a big number y. On exit y will contain the numerator of x. Return value: None Restrictions: None See also: denom, fpack. Function: void nxprime(w,x) nxprime big w,x; Module: bnprime.c Description: Find next prime number. Parameters: Two big numbers w and x. On exit x contains the next prime number greater than w. Return value: None Restrictions: None See also: prime Function: int otnum(x,f) otnum flash x; FILE *f; Module: bnio1.c Description: Output a big or flash number to the screen or to a file. If STROUT=TRUE output is redirected to the global string OBUFF[]. A flash number will be converted to radix-point representation if the global variable POINT=ON. Otherwise it will be output as a fraction. If the global variable WRAP=ON numbers too large to be represented on one line are 'wrapped around' onto the next line. Parameters: A big/flash number x and a file descriptor f. If f is stdout then output will be to the screen, otherwise to the file opened with descriptor f. Return value: Number of output characters. Restrictions: The number base specified in mirsys must be less than or equal to 256. If not, use cotnum instead. See also: innum, cinnum, cotnum. Function: void power(x,n,z,w) power int n; big x,z,w; Module: bnarth3.c Description: Raise a big number to an integer power. Parameters: Two big numbers x and z, and an integer n. On exit w=x^n If w and z are distinct, then w=x^n mod z Return value: None. Restrictions: The value of n must be positive See also: powmod, root Function: void powmod(x,y,z,w) powmod big x,y,z,w; Module: bnarth3.c Description: Raise a big number to a big power modulus another big number. Parameters: Four big numbers x,y,z and w. On exit w=x^y mod z. Return value: None Restrictions: The value of y must be positive. The parameters w and z must be distinct. See also: power, root Function: void premult(x,n,z) premult int n; big x,z; Module: bnarth1.c Description: Multiplies a big number by an integer Parameters: Two big numbers x and z, and an integer n. On exit z=n.x Return value: None Restrictions: None See also: subdiv Function: bool prime(x) prime big x; Module: bnprime.c Description: Tests whether or not a big number is prime using a probabilistic primality test. The number is assumed to be prime if it passes this test NTRY times, where NTRY is a global variable with a default initialisation in routine mirsys. Parameters: A big number x. Return value: Returns the boolean value TRUE if x is (almost certainly) prime, otherwise FALSE. Restrictions: None See also: nxprime, strongp Function: void putdig(n,x,i) putdig big x; int i,n; Module: bncore.c Description: Set a digit of a big number to a given value Parameters: A big number x, a digit number i, and its new value n. Return value: None Restrictions: The digit indicated must exist. See also: getdig, numdig. Function: bool root(x,n,z) root big x,z; int n; Module: bnarth3.c Description: Extracts lower approximation to a root of a big number. Parameters: Two big numbers x and z, and an integer n. On exit z=x^(1/n). Return value: Returns the boolean value TRUE if the root found is exact, otherwise returns FALSE. Restrictions: The value of n must be positive. If x is negative, then n must be odd. See also: power, powmod Function: void round(n,d,x) round flash x; big n,d; Module: bnround.c Description: Forms a rounded flash number from big numerator and denominator. If rounding takes place the global variable EXACT is set to FALSE. EXACT is initialised to TRUE in routine mirsys. This routine is used internally by most of the other flash arithmetic routines. Parameters: A flash number x and two big numbers n and d. On exit x=R{n/d}, that is the flash number {n/d} rounded if necessary to fit the representation. Return value: None Restrictions: The denominator must be non-zero. See also: gcd, xgcd, fpack. Function: int size(x) size big x; Module: bncore.c Description: Tries to convert big number to simple integer format. Parameters: A big number x. Return value: The value of x as an integer. If this is not possible (because x is too big) it returns the value plus or minus TOOBIG. Restrictions: None See also: - Function: int smul(x,y,z) smul int x,y,z; Module: bnsmall.c Description: Multiplies two integers mod a third Parameters: Integers x, y and z Return value: (x.y) mod z Restrictions: None See also: spmd Function: int spmd(x,y,z) spmd int x,y,z; Module: bnsmall.c Description: Raises an integer to an integer power modulus a third Parameters: Integers x, y, and z Return value: x^y mod z Restrictions: None See also: smul Function: int sqrmp(x,y) sqrmp int x,y; Module: bnsmall.c Description: Calculates the square root of an integer mod an integer prime number Parameters: An integer x and a prime number y Return value: x^(1/2) mod y, or 0 if root does not exist Restrictions: Return value unpredictable if y is not prime See also: inverse Function: void strongp(p,n) strongp big p; int n; Module: bnprime.c Description: Generate a 'strong' prime number. Useful for Public Key Cryptography programs. Parameters: A big number p and an integer n. On exit p will contain a 'strong' prime number at least n decimal digits long. Return value: None Restrictions: None. The prime p may be rather more than n digits long. See also: prime, nxprime Function: int subdiv(x,n,z) subdiv int n; big x,z; Module: bnarth1.c Description: Divide a big number by an integer. Parameters: Two big numbers x and z, and an integer n. On exit z=x/n. Return value: The integer remainder. Restrictions: The value of n must not be zero. See also: premult Function: void subtract(x,y,z) subtract big x,y,z; Module: bnarth0.c Description: Subtracts two big numbers. Parameters: Three big numbers x, y and z. On exit z=x-y. Return value: None Restrictions: None See Also: add, incr, decr. Function: int xgcd(x,y,xd,yd,z) xgcd big x,y,xd,yd,z; Module: bnxgcd.c Description: Calculates extended Greatest Common Divisor of two big numbers. Can also be used to calculate modular inverses. Note that this routine is about 8 times slower than a 'mad' operation on numbers of similar size. Parameters: Five big numbers x,y,xd,yd and z. On exit z=gcd(x,y)=x.xd+y.yd Return value: GCD as integer, if possible, otherwise TOOBIG Restrictions: If xd and yd are not distinct, only xd is returned. The GCD is only returned if z distinct from both xd and yd. See also: gcd, round Example: xgcd(x,p,x,x,x); /* x = 1/x mod p (p is prime) */ Function: void zero(x) zero flash x; Module: bncore.c Description: Sets a big or flash number to zero Parameters: A big or flash number x. Return value: None Restrictions: None See also: - Appendix IV - Example programs Note: The programs described here are of an experimental nature, and in many cases are not completely 'finished off'. For further information read the comments associated with the appropriate source file. Program: hail.c hail.c This program allows you to investigate so-called hailstone numbers, as described by Fred Gruenberger in 'Computer Recreations', Scientific American, April 1984. The procedure is simple. Starting with any number apply the following rules: (a) If it is odd, multiply it by 3 and add 1. (b) If it is even, divide it by 2. (c) Repeat the process, until the number becomes equal to 1, in which case stop. It would appear that for any initial number this process always eventually terminates, although it has not been proved that this must happen, or that the process can not get stuck in an infinite loop. What goes up, it seems, must come down. Try the program for an initial value of 27. Then try it using much bigger numbers. Program: palin.c palin.c This programs allows you to investigate palindromic reversals. See 'Computer Recreations' by Fred Gruenberger, Scientific American, April 1984. A palindromic number is one which reads the same in both directions. Start with any number and apply the following rules. (a) Add the number to the number obtained by reversing the order of the digits. Make this the new number. (b) Stop the process when the new number is palindromic. It appears that for most initial numbers this process quickly terminates. Try it for 89. Then try it for 196. Program: brute.c brute.c This program attempts to factorise a number by brute force division, using a table of small prime numbers. When attempting a difficult factorisation it makes sense to try this approach first. Use this program to factorise 12345678901234567890. Then try it on bigger random numbers. Program: brent.c brent.c This program attempts to factorise a number using the Brent-Pollard method. This method is faster at finding larger factors than the simple-minded brute force approach. However it will not always succeed, even for very simple factorisations. Use it to factorise R17, that is 11111111111111111 (seventeen ones). Then try it on larger numbers that would not yield to the brute force approach. Program: pollard.c pollard.c Another factoring program, which implements Pollard's (p-1) method, specialises in quickly finding a factor p of a number N for which (p-1) has itself only small factors. Phase 1 of this method will work if all these small factors are less than LIMIT1. If Phase 1 fails then Phase 2 searches for just one final larger factor less than LIMIT2. The constants LIMIT1 and LIMIT2 are set inside the program. Program: williams.c williams.c This program is similar to Pollards method, but can find a factor p of N for which (p+1) has only small factors. Again two phases are used. In fact this method is sometimes a (p+1) method, and sometimes a (p-1) method, so several attempts are made to find the (p+1) condition. The algorithm is rather more complex than that used in Pollards method, and is somewhat slower. Program: lenstra.c lenstra.c Recently Lenstra has discovered a new method of factorisation, generically similar to the Pollard and Williams methods, but potentially much more powerful. It works by randomly generating an Elliptic Curve, which can then be used to find a factor p of N, for which p+1-d has only small factors, where d depends on the particular curve chosen. If one curve fails then another can be tried, an option not possible with the Pollard/Williams methods. Again this is a two phase method, and although it has very good asymptotic behaviour, it is much slower than the pollard/williams for each iteration. Program: qsieve.c qsieve.c This is a very sophisticated Pomerance-Silverman-Montgomery factoring program. Its speciality is factoring all numbers (up to about sixty digits long), irrespective of the size of the factors. If the number to be factored is N, then the program actually works with a number k.N, where k is a small Knuth-Schroepel multiplier. The program itself works out the best value of k to use. Internally, the program uses a 'factor base' of small primes. The larger the number, the bigger will be this factor base. The program works by accumulating information from a number of simpler factorisations. As it progresses with these it prints out 'working...n'. When it thinks it has enough information it prints out 'trying', but these tries may be premature and may not succeed. The program will always terminate before the number n in 'working...n' reaches the size of the factor base. This program uses much more memory than any of the other example programs, particularly when factoring bigger numbers. The amount of memory that the program can take is limited by the values defined for MEM and MLF at the beginning of the program. These should be increased if possible, or reduced if your computer has insufficient memory. Use qsieve to factor 10000000000000000000000000000000009 (thirty- five digits). Program: mersenne.c mersenne.c This program generates all prime numbers of the form 2^n-1. The largest known primes have always been of this form because of the efficiency of this Lucas-Lehmer test. Program: rsakey.c rsakey.c Public Key Cryptography is a two key encipherment system with the very desirable feature that the encoding key can be made publicly available, without weakening the strength of the cipher. This program generates the 'public' encoding key and 'private' decoding key for the original Rivest-Shamir-Adleman PKS system. These keys can take a long time to generate, as they are formed from very large prime numbers, which must be generated carefully for maximum security. The program prompts for 'Minimum size of keys in decimal digits'. The security of the system depends on the difficulty of factoring the encoding 'public' key, which is formed from two large primes. The largest numbers which can be routinely factored using the most powerful computers are 100 digits long (1988). So a minimum size of 120 gives adequate security (for now!) After this program has run, the two keys are created in files PUBLIC.KEY and PRIVATE.KEY. Program: encode.c encode.c Messages or files may be encoded with this program, which uses the 'public' encoding key from the file PUBLIC.KEY, generated by the program 'rsakey', which must have been run prior to using this program. When run the user is prompted for a file to encipher. Either give the name of a text file, or press return to enter a message directly from the keyboard. In the former case the encoded output is sent to a file with the same name, but with the extension .RSA. In the latter case you are prompted for an output filename, which must be given. Text entered from the keyboard must be terminated by a CONTROL Z (end-of-file). Type out the encoded file and be impressed by how indecipherable it looks Program: decode.c decode.c Messages or files encoded using the RSA system may be decoded using this program, which uses the 'private' decoding key from the file PRIVATE.KEY generated by the program 'rsakey' which must have been run at some stage prior to using this program. When run, the user is prompted for the name of the file to be decoded. Type in the filename (without an extension - the program will assume the extension .RSA) and press return. Then the user is asked for an output filename. Either supply a filename or press return, in which case the decoded output will be sent straight to the screen. A problem with the RSA system becomes immediately apparent - decoding takes a very long time! This is particularly true for larger key sizes and long messages. Program: okakey.c okakey.c This program generates 'public' and 'private' keys for use with the Okamoto PKS system. As with the RSA system the keys are generated from large prime numbers carefully selected for certain properties, so this program takes a long time to run. A key length of 150 is adequate. The two keys are generated into files PUBLIC.KEY and PRIVATE.KEY. Program: enciph.c enciph.c This program works in an identical fashion to the program 'encode', although in this case the encoded file produced will be 1.35 times bigger than the original. Program: deciph.c deciph.c This program works in an identical fashion to the program 'decode'. However it has the advantage that it runs much more quickly. Note : The original version of this program was 'cracked' by the redoubtable Shamir. Okamoto (Electronics letters 30th July 1987, Vol. 23 No. 16 pp814-815) responded with a modified algorithm which appears to be resistant to Shamirs method of attack. This improved version has now been implemented. Over to you Shamir... Program: pi.c pi.c This program calculates pi using a Guass-Legendre O(n².log(n)) method. (Is there a more efficient way to calculate pi for moderate n?) The greater the precision specified in the call to routine 'mirsys', the more decimal place there will be in the answer (and the longer it will take). Program: roots.c roots.c This program calculates the n-th root of an input number, using Newtons method. Try it to calculate the square root of two. Again the accuracy obtained depends on the size of the flash variables, specified in routine 'mirsys'. The tendency of flash arithmetic to prefer simple numbers can be illustrated by requesting, say, the square root of 7. The program calculates this value and then squares it, to give 7 again exactly. On your pocket calculator the same result will only be obtained if clever use is made of extra (hidden) guard digits. Program: hilbert.c hilbert.c Traditionally the inversion of 'Hilbert' matrices is regarded as a tough test for any system of arithmetic. This programs solves the set of linear equations H.x = b, where H is a Hilbert matrix and b is the vector [1,1,1,1,....1], using the classical Guassian Elimination method. Program: sample.c sample.c This program is the same as that used by Brent (1978) to demonstrate some of the capabilities of his Fortran Multiprecision arithmetic package. It calculates pi, exp(pi*sqrt(163/9)) and exp(pi*sqrt(163)). Program: ratcalc.c ratcalc.c As a comprehensive and useful demonstration of flash arithmetic this program simulates a standard full-function scientific calculator. Its unique feature (besides its 36-digit accuracy) is its ability to work directly with fractions, and to handle mixed calculations involving both fractions and decimals. By using this program the user will quickly get a feel for flash arithmetic and its capabilities. Note that this program contains some non-portable code (screen handling routines) that must be tailored to each individual computer/terminal combination.